{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #剧情触发时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getTriggerTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #剧情触发时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在战略游戏中，玩家往往需要发展自己的势力来触发各种新的剧情。一个势力的主要属性有三种，分别是文明等级（<code>C</code>），资源储备（<code>R</code>）以及人口数量（<code>H</code>）。在游戏开始时（第 0 天），三种属性的值均为 0。</p>\n",
    "\n",
    "<p>随着游戏进程的进行，每一天玩家的三种属性都会对应<strong>增加</strong>，我们用一个二维数组 <code>increase</code> 来表示每天的增加情况。这个二维数组的每个元素是一个长度为 3 的一维数组，例如 <code>[[1,2,1],[3,4,2]]</code> 表示第一天三种属性分别增加 <code>1,2,1</code> 而第二天分别增加 <code>3,4,2</code>。</p>\n",
    "\n",
    "<p>所有剧情的触发条件也用一个二维数组 <code>requirements</code> 表示。这个二维数组的每个元素是一个长度为 3 的一维数组，对于某个剧情的触发条件 <code>c[i], r[i], h[i]</code>，如果当前 <code>C &gt;= c[i]</code> 且 <code>R &gt;= r[i]</code> 且 <code>H &gt;= h[i]</code> ，则剧情会被触发。</p>\n",
    "\n",
    "<p>根据所给信息，请计算每个剧情的触发时间，并以一个数组返回。如果某个剧情不会被触发，则该剧情对应的触发时间为 -1 。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入： <code>increase = [[2,8,4],[2,5,0],[10,9,8]]</code> <code>requirements = [[2,11,3],[15,10,7],[9,17,12],[8,1,14]]</code></p>\n",
    "\n",
    "<p>输出: <code>[2,-1,3,-1]</code></p>\n",
    "\n",
    "<p>解释：</p>\n",
    "\n",
    "<p>初始时，C = 0，R = 0，H = 0</p>\n",
    "\n",
    "<p>第 1 天，C = 2，R = 8，H = 4</p>\n",
    "\n",
    "<p>第 2 天，C = 4，R = 13，H = 4，此时触发剧情 0</p>\n",
    "\n",
    "<p>第 3 天，C = 14，R = 22，H = 12，此时触发剧情 2</p>\n",
    "\n",
    "<p>剧情 1 和 3 无法触发。</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入： <code>increase = [[0,4,5],[4,8,8],[8,6,1],[10,10,0]]</code> <code>requirements = [[12,11,16],[20,2,6],[9,2,6],[10,18,3],[8,14,9]]</code></p>\n",
    "\n",
    "<p>输出: <code>[-1,4,3,3,3]</code></p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入： <code>increase = [[1,1,1]]</code> <code>requirements = [[0,0,0]]</code></p>\n",
    "\n",
    "<p>输出: <code>[0]</code></p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= increase.length &lt;= 10000</code></li>\n",
    "\t<li><code>1 &lt;= requirements.length &lt;= 100000</code></li>\n",
    "\t<li><code>0 &lt;= increase[i] &lt;= 10</code></li>\n",
    "\t<li><code>0 &lt;= requirements[i] &lt;= 100000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ju-qing-hong-fa-shi-jian](https://leetcode.cn/problems/ju-qing-hong-fa-shi-jian/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ju-qing-hong-fa-shi-jian](https://leetcode.cn/problems/ju-qing-hong-fa-shi-jian/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,8,4],[2,5,0],[10,9,8]]\\n[[2,11,3],[15,10,7],[9,17,12],[8,1,14]]', '[[1,1,1]]\\n[[0,0,0]]', '[[0,4,5],[4,8,8],[8,6,1],[10,10,0]]\\n[[12,11,16],[20,2,6],[9,2,6],[10,18,3],[8,14,9]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        # 每一天玩家的三种属性都会对应增加,非递减:3个二分查找?\n",
    "        cs = [[0]*3]\n",
    "        for c in increase:\n",
    "            cs.append([0]*3)\n",
    "            for i in range(3):\n",
    "                cs[-1][i]=cs[-2][i]+c[i]\n",
    "        n=len(cs)\n",
    "        m=len(requirements)\n",
    "        res = [-1]*m\n",
    "        for i,(x,y,z) in enumerate(requirements):\n",
    "            xx = bisect_left(range(n), x,key= lambda q:cs[q][0])\n",
    "            yy = bisect_left(range(n), y,key= lambda q:cs[q][1])\n",
    "            zz = bisect_left(range(n), z,key= lambda q:cs[q][2])\n",
    "            if max(xx,yy,zz)<n:\n",
    "                res[i] = max(xx,yy,zz)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        cs = [[0] * 3]\n",
    "        for c in increase:\n",
    "            cs.append([0] * 3)\n",
    "            for i in range(3):\n",
    "                cs[-1][i] = cs[-2][i] + c[i]\n",
    "        n, m = len(cs), len(requirements)\n",
    "        ans = [-1] * m\n",
    "        for i, (x, y, z) in enumerate(requirements):\n",
    "            idx1 = bisect_left(range(n), x, key = lambda k: cs[k][0])\n",
    "            idx2 = bisect_left(range(n), y, key = lambda k: cs[k][1])\n",
    "            idx3 = bisect_left(range(n), z, key = lambda k: cs[k][2])\n",
    "            v = max(idx1, idx2, idx3)\n",
    "            if v < n:\n",
    "                ans[i] = v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        n = len(increase)\n",
    "        value = [[0] * (3) for _ in range(n+1)]\n",
    "\n",
    "        for i, diff in enumerate(increase):\n",
    "            for j in range(3):\n",
    "                value[i+1][j] = value[i][j] + diff[j]\n",
    "\n",
    "        ans = []\n",
    "        for i in range(len(requirements)):\n",
    "            time = 0\n",
    "            for j in range(3):\n",
    "                L, R = 0, n\n",
    "                while L <= R:\n",
    "                    mid = (L + R) // 2\n",
    "                    if value[mid][j] < requirements[i][j]:\n",
    "                        L = mid + 1\n",
    "                    else:\n",
    "                        R = mid - 1\n",
    "                if L == n + 1:\n",
    "                    time = -1\n",
    "                    break\n",
    "                time = max(time, L)\n",
    "            ans.append(time)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "\n",
    "        # 首先做个求和\n",
    "        n = len(increase)\n",
    "        levels = [[0,0,0] for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            for j in range(3):\n",
    "                levels[i+1][j] = levels[i][j] + increase[i][j]\n",
    "\n",
    "        # 然后接力二分查找\n",
    "        ans = []\n",
    "        for req in requirements:\n",
    "            \n",
    "            lo = 0\n",
    "            hi = n+1\n",
    "            for i in range(3):\n",
    "                while lo<hi:\n",
    "                    mi = (lo+hi)>>1\n",
    "                    if req[i] <= levels[mi][i]:\n",
    "                        hi = mi\n",
    "                    else:\n",
    "                        lo = mi + 1\n",
    "                hi = n+1\n",
    "            ans.append(lo) if lo < n+1 else ans.append(-1)\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "            \n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        [(clist.append(clist[-1] + c),rlist.append(rlist[-1] + r),hlist.append(hlist[-1] + h))for c,r,h in increase]\n",
    "        result = []\n",
    "        l = len(clist)\n",
    "        for index,(c,r,t) in enumerate(requirements):\n",
    "            m = max(left(clist,c),left(rlist,r),left(hlist,t))\n",
    "            if m != l:\n",
    "                result.append(m)\n",
    "            else:\n",
    "                result.append(-1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        n = len(increase)\n",
    "        value = [[0] * (3) for _ in range(n+1)]\n",
    "\n",
    "        for i, diff in enumerate(increase):\n",
    "            for j in range(3):\n",
    "                value[i+1][j] = value[i][j] + diff[j]\n",
    "\n",
    "        ans = []\n",
    "        for i in range(len(requirements)):\n",
    "            time = 0\n",
    "            for j in range(3):\n",
    "                L, R = 0, n\n",
    "                while L <= R:\n",
    "                    mid = (L + R) // 2\n",
    "                    if value[mid][j] < requirements[i][j]:\n",
    "                        L = mid + 1\n",
    "                    else:\n",
    "                        R = mid - 1\n",
    "                if L == n + 1:\n",
    "                    time = -1\n",
    "                    break\n",
    "                time = max(time, L)\n",
    "            ans.append(time)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        res = [[0, 0, 0]]\n",
    "        a, b, c = 0, 0, 0\n",
    "        for x, y, z in increase:\n",
    "            a += x\n",
    "            b += y\n",
    "            c += z\n",
    "            res.append([a, b, c])\n",
    "        n = len(res)\n",
    "        ans = []\n",
    "\n",
    "        def f(i, j, k):\n",
    "            a, b, c = res[-1]\n",
    "            if i > a or j > b or k > c:\n",
    "                return -1\n",
    "            low, high = 0, n - 1\n",
    "            ret = n - 1\n",
    "            while low <= high:\n",
    "                mid = (low + high) // 2\n",
    "                if res[mid][0] < i or res[mid][1] < j or res[mid][2] < k:\n",
    "                    low = mid + 1\n",
    "                else:\n",
    "                    ret = mid \n",
    "                    high = mid - 1\n",
    "            return ret\n",
    "        \n",
    "        for i, j, k in requirements:\n",
    "            ans.append(f(i, j, k))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        #首先利用前缀和计算每天属性值，\n",
    "        #raran然后执行三次二分查找\n",
    "        cur=[[0]*3]\n",
    "        for a in increase:\n",
    "            cur.append([0]*3)\n",
    "            for i in range(3):cur[-1][i]=cur[-2][i]+a[i]\n",
    "        n=len(cur)\n",
    "        ans=[-1]*len(requirements)\n",
    "        for idx,(a,b,c) in enumerate(requirements):\n",
    "            i=bisect_left(range(n),a,key=lambda x:cur[x][0])\n",
    "            j=bisect_left(range(n),b,key=lambda x:cur[x][1])\n",
    "            k=bisect_left(range(n),c,key=lambda x:cur[x][2])\n",
    "            if max(i,j,k)<n:\n",
    "                # ans[idx]=min(i,j,k)#只满足一个即可触发，使用min\n",
    "                ans[idx]=max(i,j,k)#都满足，才能触发，使用max\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        a = [0]\n",
    "        b = [0]\n",
    "        c = [0]\n",
    "        ans = [-1]*len(requirements)\n",
    "        for i in increase:\n",
    "            a.append(a[-1]+i[0])\n",
    "            b.append(b[-1]+i[1])\n",
    "            c.append(c[-1]+i[2])\n",
    "        k = len(a)\n",
    "        for i in range(len(requirements)):\n",
    "            x = bisect.bisect_left(a,requirements[i][0])\n",
    "            y = bisect.bisect_left(b,requirements[i][1])\n",
    "            z = bisect.bisect_left(c,requirements[i][2])\n",
    "            if max(x,y,z) <k:\n",
    "                ans[i] = max(x,y,z)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "\n",
    "        increase.insert(0, [0, 0, 0])\n",
    "\n",
    "        for i in range(1, len(increase)):\n",
    "            for j in range(3):\n",
    "                increase[i][j] += increase[i - 1][j]\n",
    "\n",
    "        def find_first_max(left: int, i: int, target: int) -> int:\n",
    "\n",
    "            left = left\n",
    "            right = len(increase) - 1\n",
    "            if increase[right][i] < target:\n",
    "                return len(increase)\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if increase[mid][i] >= target:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return right\n",
    "\n",
    "        ans = [0] * len(requirements)\n",
    "        for i, requirement in enumerate(requirements):\n",
    "            C = find_first_max(0, 0, requirement[0])\n",
    "            if C == len(increase):\n",
    "                ans[i] = -1\n",
    "                continue\n",
    "            R = find_first_max(C, 1, requirement[1])\n",
    "            if R == len(increase):\n",
    "                ans[i] = -1\n",
    "                continue\n",
    "            H = find_first_max(R, 2, requirement[2])\n",
    "            if H == len(increase):\n",
    "                ans[i] = -1\n",
    "                continue\n",
    "            ans[i] = H\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[[2,2,2],[3,3,3]]\n",
    "[[1,1,1],[2,2,2]]\n",
    "\n",
    "[[2,8,4],[2,5,0],[10,9,8]]\n",
    "[[2,11,3],[15,10,7],[9,17,12],[8,1,14]]\n",
    "[[0,4,5],[4,8,8],[8,6,1],[10,10,0]]\n",
    "[[12,11,16],[20,2,6],[9,2,6],[10,18,3],[8,14,9]]\n",
    "[[1,1,1]]\n",
    "[[0,0,0]]\n",
    "\n",
    "1 <= increase.length <= 10000\n",
    "1 <= requirements.length <= 100000\n",
    "0 <= increase[i] <= 10\n",
    "0 <= requirements[i] <= 100000\n",
    "\n",
    "数组,二分查找,排序\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        res = [0]*len(requirements)\n",
    "        for i in range(1, len(increase)):\n",
    "            for j in range(len(increase[i])):\n",
    "                increase[i][j] += increase[i-1][j]\n",
    "        for i in range(len(requirements)):\n",
    "            if sum(requirements[i]) == 0:\n",
    "                res[i] = 0\n",
    "                continue\n",
    "            l, r = 0, len(increase)\n",
    "            while l < r:\n",
    "                m = l + ((r-l) >> 1)\n",
    "                if self.check(increase, m, requirements[i]):\n",
    "                    r = m\n",
    "                else:\n",
    "                    l = m+1\n",
    "            if l < len(increase):\n",
    "                res[i] = l+1\n",
    "            else:\n",
    "                res[i] = -1\n",
    "        return res\n",
    "    def check(self, increase, idx, req):\n",
    "        return increase[idx][0] >= req[0] and \\\n",
    "               increase[idx][1] >= req[1] and \\\n",
    "               increase[idx][2] >= req[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        cs = [[0]*3]\n",
    "        for c in increase:\n",
    "            cs.append([0]*3)\n",
    "            for i in range(3):\n",
    "                cs[-1][i]=cs[-2][i]+c[i]\n",
    "        n=len(cs)\n",
    "        m=len(requirements)\n",
    "        res = [-1]*m\n",
    "        for i,(x,y,z) in enumerate(requirements):\n",
    "            xx = bisect_left(range(n), x,key= lambda q:cs[q][0])\n",
    "            yy = bisect_left(range(n), y,key= lambda q:cs[q][1])\n",
    "            zz = bisect_left(range(n), z,key= lambda q:cs[q][2])\n",
    "            if max(xx,yy,zz)<n:\n",
    "                res[i] = max(xx,yy,zz)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase, requirements):\n",
    "        n = len(requirements)\n",
    "        m = len(increase)\n",
    "        ans = [-1] * n\n",
    "        req_res = [list(range(n)) for _ in range(3)]\n",
    "        for i in range(3):\n",
    "            req_res[i].sort(key = lambda r:requirements[r][i])\n",
    "        res = [0,0,0]\n",
    "        cur_idx = [0,0,0]\n",
    "        for i in range(-1,m):\n",
    "            if i >= 0:\n",
    "                for j in range(3):\n",
    "                    res[j] += increase[i][j]\n",
    "            for j in range(3):\n",
    "                while cur_idx[j] < n and res[j] >= requirements[req_res[j][cur_idx[j]]][j]:\n",
    "                    if ans[req_res[j][cur_idx[j]]] != -1:\n",
    "                        cur_idx[j] += 1\n",
    "                        continue\n",
    "                    if all([res[k] >= requirements[req_res[j][cur_idx[j]]][k] for k in range(3)]):\n",
    "                        ans[req_res[j][cur_idx[j]]] = i + 1\n",
    "                    cur_idx[j] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        for c,r,h in increase:\n",
    "            clist.append(clist[-1] + c)\n",
    "            rlist.append(rlist[-1] + r)\n",
    "            hlist.append(hlist[-1] + h)\n",
    "        result = [-1] * len(requirements)\n",
    "        l = len(clist)\n",
    "        for index,require in enumerate(requirements):\n",
    "            \n",
    "            ct = left(clist,require[0])\n",
    "            rt = left(rlist,require[1])\n",
    "            ht = left(hlist,require[2])\n",
    "            m = max(ct,rt,ht)\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        def binarySearch(kl,item,end,start=0):\n",
    "            if kl[-1] < item:\n",
    "                return -1\n",
    "            if kl[0] >= item:\n",
    "                return 0\n",
    "            b = (start + end) // 2\n",
    "            if kl[b] < item and kl[b+1] >= item:\n",
    "                return b + 1\n",
    "            if kl[b] >= item:\n",
    "                return binarySearch(kl,item,b,start)\n",
    "            else:\n",
    "                return binarySearch(kl,item,end,b)\n",
    "        \n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        for c,r,h in increase:\n",
    "            clist.append(clist[-1] + c)\n",
    "            rlist.append(rlist[-1] + r)\n",
    "            hlist.append(hlist[-1] + h)\n",
    "        l = len(requirements)\n",
    "        result = [-1] * l\n",
    "        for index,require in enumerate(requirements):\n",
    "            end = len(clist)\n",
    "            ct = binarySearch(clist,require[0],end)\n",
    "            rt = binarySearch(rlist,require[1],end)\n",
    "            ht = binarySearch(hlist,require[2],end)\n",
    "            minT = min(ct,rt,ht)\n",
    "            if minT == -1:\n",
    "                result[index] = -1\n",
    "            else:\n",
    "                result[index] = max(ct,rt,ht)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        for c,r,h in increase:\n",
    "            clist.append(clist[-1] + c)\n",
    "            rlist.append(rlist[-1] + r)\n",
    "            hlist.append(hlist[-1] + h)\n",
    "        l = len(requirements)\n",
    "        result = [-1] * l\n",
    "        for index,require in enumerate(requirements):\n",
    "            l = len(clist)\n",
    "            ct = left(clist,require[0])\n",
    "            rt = left(rlist,require[1])\n",
    "            ht = left(hlist,require[2])\n",
    "            m = max(ct,rt,ht)\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        for c,r,h in increase:\n",
    "            clist.append(clist[-1] + c)\n",
    "            rlist.append(rlist[-1] + r)\n",
    "            hlist.append(hlist[-1] + h)\n",
    "        result = [-1] * len(requirements)\n",
    "        l = len(clist)\n",
    "        for index,(c,r,t) in enumerate(requirements):\n",
    "            ct = left(clist,c)\n",
    "            rt = left(rlist,r)\n",
    "            ht = left(hlist,t)\n",
    "            m = max(ct,rt,ht)\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        n, m = len(increase), len(requirements)\n",
    "        prefix = [\n",
    "            list(accumulate(elem, initial=0)) \n",
    "            for elem in zip(*increase)\n",
    "        ]\n",
    "        \n",
    "        res = [-1] * m\n",
    "\n",
    "        for i, elem in enumerate(requirements):\n",
    "            if (idx := max(bisect_left(prefix[j], x) for j, x in enumerate(elem))) <= n:\n",
    "                res[i] = idx\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        [(clist.append(clist[-1] + c),rlist.append(rlist[-1] + r),hlist.append(hlist[-1] + h))for c,r,h in increase]\n",
    "        result = [-1] * len(requirements)\n",
    "        l = len(clist)\n",
    "        for index,(c,r,t) in enumerate(requirements):\n",
    "            ct = left(clist,c)\n",
    "            rt = left(rlist,r)\n",
    "            ht = left(hlist,t)\n",
    "            m = max(ct,rt,ht)\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        for c,r,h in increase:\n",
    "            clist.append(clist[-1] + c)\n",
    "            rlist.append(rlist[-1] + r)\n",
    "            hlist.append(hlist[-1] + h)\n",
    "        result = [-1] * len(requirements)\n",
    "        l = len(clist)\n",
    "        for index,require in enumerate(requirements):\n",
    "            ct = left(clist,require[0])\n",
    "            rt = left(rlist,require[1])\n",
    "            ht = left(hlist,require[2])\n",
    "            m = max(ct,rt,ht)\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        def binarySearch(kl,item,end,start=0):\n",
    "            if kl[-1] < item:\n",
    "                return -1\n",
    "            if kl[0] >= item:\n",
    "                return 0\n",
    "            b = (start + end) // 2\n",
    "            if kl[b] < item and kl[b+1] >= item:\n",
    "                return b + 1\n",
    "            if kl[b] >= item:\n",
    "                return binarySearch(kl,item,b,start)\n",
    "            else:\n",
    "                return binarySearch(kl,item,end,b)\n",
    "        \n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        for c,r,h in increase:\n",
    "            clist.append(clist[-1] + c)\n",
    "            rlist.append(rlist[-1] + r)\n",
    "            hlist.append(hlist[-1] + h)\n",
    "        l = len(requirements)\n",
    "        result = [-1] * l\n",
    "        for index,require in enumerate(requirements):\n",
    "            end = len(clist)\n",
    "            ct = binarySearch(clist,require[0],end)\n",
    "            rt = binarySearch(rlist,require[1],end)\n",
    "            ht = binarySearch(hlist,require[2],end)\n",
    "            minT = min(ct,rt,ht)\n",
    "            if minT == -1:\n",
    "                result[index] = -1\n",
    "            else:\n",
    "                result[index] = max(ct,rt,ht)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        for c,r,h in increase:\n",
    "            clist.append(clist[-1] + c)\n",
    "            rlist.append(rlist[-1] + r)\n",
    "            hlist.append(hlist[-1] + h)\n",
    "        result = [-1] * len(requirements)\n",
    "        l = len(clist)\n",
    "        for index,(c,r,t) in enumerate(requirements):\n",
    "            ct = left(clist,c)\n",
    "            rt = left(rlist,r)\n",
    "            ht = left(hlist,t)\n",
    "            m = max(ct,rt,ht)\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        def binarySearch(kl,item,end,start=0):\n",
    "            if kl[-1] < item:\n",
    "                return -1\n",
    "            if kl[0] >= item:\n",
    "                return 0\n",
    "            b = (start + end) // 2\n",
    "            if kl[b] < item and kl[b+1] >= item:\n",
    "                return b + 1\n",
    "            if kl[b] >= item:\n",
    "                return binarySearch(kl,item,b,start)\n",
    "            else:\n",
    "                return binarySearch(kl,item,end,b)\n",
    "        \n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        for c,r,h in increase:\n",
    "            clist.append(clist[-1] + c)\n",
    "            rlist.append(rlist[-1] + r)\n",
    "            hlist.append(hlist[-1] + h)\n",
    "        l = len(requirements)\n",
    "        result = [-1] * l\n",
    "        for index,require in enumerate(requirements):\n",
    "            end = len(clist)\n",
    "            ct = binarySearch(clist,require[0],end)\n",
    "            rt = binarySearch(rlist,require[1],end)\n",
    "            ht = binarySearch(hlist,require[2],end)\n",
    "            minT = min(ct,rt,ht)\n",
    "            if minT == -1:\n",
    "                result[index] = -1\n",
    "            else:\n",
    "                result[index] = max(ct,rt,ht)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        m = len(increase)\n",
    "        for i in range(1, m):\n",
    "            increase[i][0] += increase[i-1][0]\n",
    "            increase[i][1] += increase[i-1][1]\n",
    "            increase[i][2] += increase[i-1][2]\n",
    "\n",
    "        n = len(requirements)\n",
    "        res = [-1]*n\n",
    "\n",
    "        indices = list(range(n))\n",
    "        indices.sort(key=lambda i:requirements[i])\n",
    "\n",
    "        def find(start, end, arr, target):\n",
    "            s = start\n",
    "            e = end\n",
    "            while s <= e:\n",
    "                mid = (s+e)//2\n",
    "                if arr[mid] >= target:\n",
    "                    e = mid - 1\n",
    "                else:\n",
    "                    s = mid + 1\n",
    "            if arr[mid] < target:\n",
    "                mid += 1\n",
    "            return mid\n",
    "\n",
    "        def get_trigger(caps, reqs):\n",
    "            indices = list(range(n))\n",
    "            indices.sort(key=lambda i: reqs[i])\n",
    "            trigs = [0 for _ in range(n)]\n",
    "            idx = indices[0]\n",
    "            if reqs[idx] == 0:\n",
    "                trigs[idx] = -1\n",
    "            else:\n",
    "                trigs[idx] = find(0, m-1, caps, reqs[idx])\n",
    "            for i in range(1, n):\n",
    "                idx1 = indices[i]\n",
    "                idx0 = indices[i-1]\n",
    "                if reqs[idx1] == reqs[idx0]:\n",
    "                    trigs[idx1] = trigs[idx0]\n",
    "                elif trigs[idx0] == m:\n",
    "                    trigs[idx1] = m\n",
    "                else:\n",
    "                    trigs[idx1] = find(trigs[idx0] if trigs[idx0]>=0 else 0, m-1, caps, reqs[idx1])\n",
    "            return trigs\n",
    "\n",
    "        trig_lists = [get_trigger([inc[i] for inc in increase], [req[i] for req in requirements]) for i in range(3)]\n",
    "        res = [-1]*n\n",
    "        for i in range(n):\n",
    "            trig = max(trig_list[i] for trig_list in trig_lists)\n",
    "            if trig == m:\n",
    "                res[i] = -1\n",
    "            else:\n",
    "                res[i] = trig + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        def binarySearch(kl,item,end,start=0):\n",
    "            if kl[-1] < item:\n",
    "                return -1\n",
    "            if kl[0] >= item:\n",
    "                return 0\n",
    "            b = (start + end) // 2\n",
    "            if kl[b] < item and kl[b+1] >= item:\n",
    "                return b + 1\n",
    "            if kl[b] >= item:\n",
    "                return binarySearch(kl,item,b,start)\n",
    "            else:\n",
    "                return binarySearch(kl,item,end,b)\n",
    "        \n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        for c,r,h in increase:\n",
    "            clist.append(clist[-1] + c)\n",
    "            rlist.append(rlist[-1] + r)\n",
    "            hlist.append(hlist[-1] + h)\n",
    "        l = len(requirements)\n",
    "        result = [-1] * l\n",
    "        for index,require in enumerate(requirements):\n",
    "            end = len(clist)\n",
    "            ct = binarySearch(clist,require[0],end)\n",
    "            rt = binarySearch(rlist,require[1],end)\n",
    "            ht = binarySearch(hlist,require[2],end)\n",
    "            minT = min(ct,rt,ht)\n",
    "            if minT == -1:\n",
    "                result[index] = -1\n",
    "            else:\n",
    "                result[index] = max(ct,rt,ht)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        [(clist.append(clist[-1] + c),rlist.append(rlist[-1] + r),hlist.append(hlist[-1] + h))for c,r,h in increase]\n",
    "        result = [-1] * len(requirements)\n",
    "        l = len(clist)\n",
    "        for index,(c,r,t) in enumerate(requirements):\n",
    "            ct = left(clist,c)\n",
    "            rt = left(rlist,r)\n",
    "            ht = left(hlist,t)\n",
    "            m = max(ct,rt,ht)\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(\n",
    "        self, \n",
    "        increase: List[List[int]], \n",
    "        requirements: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "\n",
    "        n, m = len(increase), len(requirements)\n",
    "\n",
    "        prefix = [\n",
    "            list(accumulate(elem, initial=0)) \n",
    "            for elem in zip(*increase)\n",
    "        ]\n",
    "        res = [-1] * m\n",
    "\n",
    "        for i, elem in enumerate(requirements):\n",
    "            idx = max(bisect_left(prefix[j], x) for j, x in enumerate(elem))\n",
    "            if idx <= n:\n",
    "                res[i] = idx\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def getTriggerTime(self, day_increase, story_requires):\n",
    "        \"\"\"\n",
    "        :type day_increase: List[List[int]]\n",
    "        :type story_requires: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        a = [0 for i in range(3)]\n",
    "        #将剧情的下标记录在story中，方便映射结果\n",
    "        story_requires = [x + [i] for i, x in enumerate(story_requires)]\n",
    "        #将requirements按三种维度分别排序，得到 s\n",
    "        s = [sorted(story_requires, key=lambda x: x[i]) for i in range(3)]\n",
    "        index = [0 for i in range(3)]\n",
    "\n",
    "        n = len(story_requires)\n",
    "        trigger = [0 for i in range(n)]\n",
    "        ans = [-1 for i in range(n)]\n",
    "        #枚举每一天\n",
    "        for d, (na,nb,nc) in enumerate(day_increase):\n",
    "            #计算当天的属性\n",
    "            a[0] += na; a[1] += nb; a[2] += nc\n",
    "            #遍历三种属性的排序序列，计算当前可以被触发的剧情\n",
    "            for i in range(3):\n",
    "                while index[i] < n and a[i] >= s[i][index[i]][i]:\n",
    "                    trigger[s[i][index[i]][-1]] += 1\n",
    "                    #如果某个剧情触发次数等于3次(三种属性均触发，剧情被实际触发)\n",
    "                    if trigger[s[i][index[i]][-1]] == 3:\n",
    "                        ans[s[i][index[i]][-1]] = d + 1\n",
    "                    index[i] += 1\n",
    "        #第0天单独考虑\n",
    "        for i, (na, nb, nc, _) in enumerate(story_requires):\n",
    "            if na == 0 and nb == 0 and nc == 0:\n",
    "                ans[_] = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(\n",
    "        self, \n",
    "        increase: List[List[int]], \n",
    "        requirements: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "\n",
    "        n, m = len(increase), len(requirements)\n",
    "\n",
    "        prefix = [\n",
    "            list(accumulate(elem, initial=0)) \n",
    "            for elem in zip(*increase)\n",
    "        ]\n",
    "        res = [-1] * m\n",
    "\n",
    "        for i, elem in enumerate(requirements):\n",
    "            if (idx := max(bisect_left(prefix[j], x) for j, x in enumerate(elem))) <= n:\n",
    "                res[i] = idx\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        for c,r,h in increase:\n",
    "            clist.append(clist[-1] + c)\n",
    "            rlist.append(rlist[-1] + r)\n",
    "            hlist.append(hlist[-1] + h)\n",
    "        result = [-1] * len(requirements)\n",
    "        l = len(clist)\n",
    "        for index,(c,r,t) in enumerate(requirements):\n",
    "            ct = left(clist,c)\n",
    "            rt = left(rlist,r)\n",
    "            ht = left(hlist,t)\n",
    "            m = max(ct,rt,ht)\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        for c,r,h in increase:\n",
    "            clist.append(clist[-1] + c)\n",
    "            rlist.append(rlist[-1] + r)\n",
    "            hlist.append(hlist[-1] + h)\n",
    "        l = len(requirements)\n",
    "        result = [-1] * l\n",
    "        for index,require in enumerate(requirements):\n",
    "            l = len(clist)\n",
    "            ct = left(clist,require[0])\n",
    "            rt = left(rlist,require[1])\n",
    "            ht = left(hlist,require[2])\n",
    "            m = max(ct,rt,ht)\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def getTriggerTime(self, day_increase, story_requires):\n",
    "        \"\"\"\n",
    "        :type day_increase: List[List[int]]\n",
    "        :type story_requires: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        a = [0 for i in range(3)]\n",
    "        #将剧情的下标记录在story中，方便映射结果\n",
    "        story_requires = [x + [i] for i, x in enumerate(story_requires)]\n",
    "        #将requirements按三种维度分别排序，得到 s\n",
    "        s = [sorted(story_requires, key=lambda x: x[i]) for i in range(3)]\n",
    "        index = [0 for i in range(3)]\n",
    "\n",
    "        n = len(story_requires)\n",
    "        trigger = [0 for i in range(n)]\n",
    "        ans = [-1 for i in range(n)]\n",
    "        #枚举每一天\n",
    "        for d, (na,nb,nc) in enumerate(day_increase):\n",
    "            #计算当天的属性\n",
    "            a[0] += na; a[1] += nb; a[2] += nc\n",
    "            #遍历三种属性的排序序列，计算当前可以被触发的剧情\n",
    "            for i in range(3):\n",
    "                while index[i] < n and a[i] >= s[i][index[i]][i]:\n",
    "                    trigger[s[i][index[i]][-1]] += 1\n",
    "                    #如果某个剧情触发次数等于3次(三种属性均触发，剧情被实际触发)\n",
    "                    if trigger[s[i][index[i]][-1]] == 3:\n",
    "                        ans[s[i][index[i]][-1]] = d + 1\n",
    "                    index[i] += 1\n",
    "        #第0天单独考虑\n",
    "        for i, (na, nb, nc, _) in enumerate(story_requires):\n",
    "            if na == 0 and nb == 0 and nc == 0:\n",
    "                ans[_] = 0\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        a = [0 for i in range(3)]\n",
    "        #将剧情的下标记录在story中，方便映射结果\n",
    "        requirements = [x + [i] for i, x in enumerate(requirements)]\n",
    "        #将requirements按三种维度分别排序，得到 s\n",
    "        s = [sorted(requirements, key=lambda x: x[i]) for i in range(3)]\n",
    "        index = [0 for i in range(3)]\n",
    "\n",
    "        n = len(requirements)\n",
    "        trigger = [0 for i in range(n)]\n",
    "        ans = [-1 for i in range(n)]\n",
    "        #枚举每一天\n",
    "        for d, (na,nb,nc) in enumerate(increase):\n",
    "            #计算当天的属性\n",
    "            a[0] += na; a[1] += nb; a[2] += nc\n",
    "            #遍历三种属性的排序序列，计算当前可以被触发的剧情\n",
    "            for i in range(3):\n",
    "                while index[i] < n and a[i] >= s[i][index[i]][i]:\n",
    "                    trigger[s[i][index[i]][-1]] += 1\n",
    "                    #如果某个剧情触发次数等于3次(三种属性均触发，剧情被实际触发)\n",
    "                    if trigger[s[i][index[i]][-1]] == 3:\n",
    "                        ans[s[i][index[i]][-1]] = d + 1\n",
    "                    index[i] += 1\n",
    "        #第0天单独考虑\n",
    "        for i, (na, nb, nc, _) in enumerate(requirements):\n",
    "            if na == 0 and nb == 0 and nc == 0:\n",
    "                ans[_] = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def getTriggerTime(self, day_increase, story_requires):\n",
    "        \"\"\"\n",
    "        :type day_increase: List[List[int]]\n",
    "        :type story_requires: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        a = [0 for i in range(3)]\n",
    "        #将剧情的下标记录在story中，方便映射结果\n",
    "        story_requires = [x + [i] for i, x in enumerate(story_requires)]\n",
    "        #将requirements按三种维度分别排序，得到 s\n",
    "        s = [sorted(story_requires, key=lambda x: x[i]) for i in range(3)]\n",
    "        index = [0 for i in range(3)]\n",
    "\n",
    "        n = len(story_requires)\n",
    "        trigger = [0 for i in range(n)]\n",
    "        ans = [-1 for i in range(n)]\n",
    "        #枚举每一天\n",
    "        for d, (na,nb,nc) in enumerate(day_increase):\n",
    "            #计算当天的属性\n",
    "            a[0] += na; a[1] += nb; a[2] += nc\n",
    "            #遍历三种属性的排序序列，计算当前可以被触发的剧情\n",
    "            for i in range(3):\n",
    "                while index[i] < n and a[i] >= s[i][index[i]][i]:\n",
    "                    trigger[s[i][index[i]][-1]] += 1\n",
    "                    #如果某个剧情触发次数等于3次(三种属性均触发，剧情被实际触发)\n",
    "                    if trigger[s[i][index[i]][-1]] == 3:\n",
    "                        ans[s[i][index[i]][-1]] = d + 1\n",
    "                    index[i] += 1\n",
    "        #第0天单独考虑\n",
    "        for i, (na, nb, nc, _) in enumerate(story_requires):\n",
    "            if na == 0 and nb == 0 and nc == 0:\n",
    "                ans[_] = 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def getTriggerTime(self, day_increase, story_requires):\n",
    "        \"\"\"\n",
    "        :type day_increase: List[List[int]]\n",
    "        :type story_requires: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        a = [0 for i in range(3)]\n",
    "        #将剧情的下标记录在story中，方便映射结果\n",
    "        story_requires = [x + [i] for i, x in enumerate(story_requires)]\n",
    "        #将requirements按三种维度分别排序，得到 s\n",
    "        s = [sorted(story_requires, key=lambda x: x[i]) for i in range(3)]\n",
    "        index = [0 for i in range(3)]\n",
    "\n",
    "        n = len(story_requires)\n",
    "        trigger = [0 for i in range(n)]\n",
    "        ans = [-1 for i in range(n)]\n",
    "        #枚举每一天\n",
    "        for d, (na,nb,nc) in enumerate(day_increase):\n",
    "            #计算当天的属性\n",
    "            a[0] += na; a[1] += nb; a[2] += nc\n",
    "            #遍历三种属性的排序序列，计算当前可以被触发的剧情\n",
    "            for i in range(3):\n",
    "                while index[i] < n and a[i] >= s[i][index[i]][i]:\n",
    "                    trigger[s[i][index[i]][-1]] += 1\n",
    "                    #如果某个剧情触发次数等于3次(三种属性均触发，剧情被实际触发)\n",
    "                    if trigger[s[i][index[i]][-1]] == 3:\n",
    "                        ans[s[i][index[i]][-1]] = d + 1\n",
    "                    index[i] += 1\n",
    "        #第0天单独考虑\n",
    "        for i, (na, nb, nc, _) in enumerate(story_requires):\n",
    "            if na == 0 and nb == 0 and nc == 0:\n",
    "                ans[_] = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        return (lambda Z, n: list(map(lambda x: -1 if x == n else x, map(max, *([bisect_left(Z[i], r[i]) for r in requirements] for i in range(3))))))(list(map(lambda *x: [0] + list(accumulate(x)), *increase)), len(increase) + 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        n=len(increase)\n",
    "        pre1=[0]*(n+1)\n",
    "        pre2=[0]*(n+1)\n",
    "        pre3=[0]*(n+1)\n",
    "        for i in range (0,n):\n",
    "            pre1[i+1]=pre1[i]+increase[i][0]\n",
    "            pre2[i+1]=pre2[i]+increase[i][1]\n",
    "            pre3[i+1]=pre3[i]+increase[i][2]\n",
    "        ans=[]\n",
    "        for x,y,z in requirements:\n",
    "            u=bisect.bisect_left(pre1,x)\n",
    "            v=bisect.bisect_left(pre2,y)\n",
    "            w=bisect.bisect_left(pre3,z)\n",
    "            if max([u,v,w])==n+1:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(max([u,v,w]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        [(clist.append(clist[-1] + c),rlist.append(rlist[-1] + r),hlist.append(hlist[-1] + h))for c,r,h in increase]\n",
    "        result = [-1] * len(requirements)\n",
    "        l = len(clist)\n",
    "        for index,(c,r,t) in enumerate(requirements):\n",
    "            m = max(left(clist,c),left(rlist,r),left(hlist,t))\n",
    "            if m != len(clist):\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        [(clist.append(clist[-1] + c),rlist.append(rlist[-1] + r),hlist.append(hlist[-1] + h))for c,r,h in increase]\n",
    "        result = [-1] * len(requirements)\n",
    "        l = len(clist)\n",
    "        for index,(c,r,t) in enumerate(requirements):\n",
    "            ct,rt,ht = left(clist,c),left(rlist,r),left(hlist,t)\n",
    "            m = max(ct,rt,ht)\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        n = len(increase) + 1\n",
    "        C, R, H = [0], [0], [0]\n",
    "        for c, r, h in increase:\n",
    "            C.append(C[-1] + c)\n",
    "            R.append(R[-1] + r)\n",
    "            H.append(H[-1] + h)\n",
    "        res = []\n",
    "        for rc, rr, rh in requirements:\n",
    "            resC = bisect.bisect_left(C, rc)\n",
    "            resR = bisect.bisect_left(R, rr)\n",
    "            resH = bisect.bisect_left(H, rh)\n",
    "            r = max(resC, resR, resH)\n",
    "            if r == n:\n",
    "                r = -1\n",
    "            res.append(r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        [(clist.append(clist[-1] + c),rlist.append(rlist[-1] + r),hlist.append(hlist[-1] + h))for c,r,h in increase]\n",
    "        result = [-1] * len(requirements)\n",
    "        l = len(clist)\n",
    "        for index,(c,r,t) in enumerate(requirements):\n",
    "            ct = left(clist,c)\n",
    "            rt = left(rlist,r)\n",
    "            ht = left(hlist,t)\n",
    "            m = max(ct,rt,ht)\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        [(clist.append(clist[-1] + c),rlist.append(rlist[-1] + r),hlist.append(hlist[-1] + h))for c,r,h in increase]\n",
    "        result = [-1] * len(requirements)\n",
    "        l = len(clist)\n",
    "        for index,(c,r,t) in enumerate(requirements):\n",
    "            m = max(left(clist,c),left(rlist,r),left(hlist,t))\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        n = len(increase) + 1\n",
    "        res = []\n",
    "        C = [0]\n",
    "        R = [0]\n",
    "        H = [0]\n",
    "        for c,r,h in increase:\n",
    "            C.append(C[-1] + c)\n",
    "            R.append(R[-1] + r)\n",
    "            H.append(H[-1] + h)\n",
    "        for cc,rr,hh in requirements:\n",
    "            bc = bisect.bisect_left(C, cc)\n",
    "            br = bisect.bisect_left(R, rr)\n",
    "            bh = bisect.bisect_left(H, hh)\n",
    "            m = max(bc, br, bh)\n",
    "            if m == n:\n",
    "                m = -1\n",
    "            res.append(m)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        length = len(increase)\n",
    "        C, R, H = [0], [0], [0]\n",
    "        temp_c, temp_r, temp_h = 0, 0, 0\n",
    "        ans = []\n",
    "        for l in increase:\n",
    "            temp_c += l[0]\n",
    "            temp_h += l[1]\n",
    "            temp_r += l[2]\n",
    "            C.append(temp_c)\n",
    "            H.append(temp_h)\n",
    "            R.append(temp_r)\n",
    "        for requirement in requirements:\n",
    "            index1, index2, index3 = self.bisect_left(C, requirement[0]), self.bisect_left(H, requirement[1]), self.bisect_left(R, requirement[2])\n",
    "            temp = max(index1, index2, index3)\n",
    "            if temp > length:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(temp)\n",
    "        return ans\n",
    "\n",
    "    def bisect_left(self, target_list, target):\n",
    "        if target > target_list[-1]:\n",
    "            return len(target_list)\n",
    "        if target < target_list[0]:\n",
    "            return 0\n",
    "        first, last = 0, len(target_list)-1\n",
    "        while first <= last:\n",
    "            mid = (first + last) // 2\n",
    "            if target <= target_list[mid]:\n",
    "                last = mid - 1\n",
    "            else:\n",
    "                first = mid + 1\n",
    "        return first\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        x, y, z = [], [], []\n",
    "        nx = ny = nz = 0\n",
    "        for dx, dy, dz in increase:\n",
    "            x.append(nx)\n",
    "            y.append(ny)\n",
    "            z.append(nz)\n",
    "            nx += dx\n",
    "            ny += dy\n",
    "            nz += dz\n",
    "        x.append(nx)\n",
    "        y.append(ny)\n",
    "        z.append(nz)\n",
    "        \n",
    "        ans = []\n",
    "        for rx, ry, rz in requirements:\n",
    "            tmp = max(bisect_left(x, rx), bisect_left(y, ry), bisect_left(z, rz))\n",
    "            if tmp >= len(x):ans.append(-1)\n",
    "            else:ans.append(tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        n = len(increase) + 1\n",
    "        C, R, H = [0], [0], [0]\n",
    "        for c, r, h in increase:\n",
    "            C.append(C[-1] + c)\n",
    "            R.append(R[-1] + r)\n",
    "            H.append(H[-1] + h)\n",
    "        res = []\n",
    "        for rc, rr, rh in requirements:\n",
    "            resC = bisect.bisect_left(C, rc)\n",
    "            resR = bisect.bisect_left(R, rr)\n",
    "            resH = bisect.bisect_left(H, rh)\n",
    "            r = max(resC, resR, resH)\n",
    "            if r == n:\n",
    "                r = -1\n",
    "            res.append(r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        length = len(increase)\n",
    "        C, R, H = [0], [0], [0]\n",
    "        temp_c, temp_r, temp_h = 0, 0, 0\n",
    "        ans = []\n",
    "        for l in increase:\n",
    "            temp_c += l[0]\n",
    "            temp_h += l[1]\n",
    "            temp_r += l[2]\n",
    "            C.append(temp_c)\n",
    "            H.append(temp_h)\n",
    "            R.append(temp_r)\n",
    "        for requirement in requirements:\n",
    "            index1, index2, index3 = bisect_left(C, requirement[0]), bisect_left(H, requirement[1]), bisect_left(R, requirement[2])\n",
    "            temp = max(index1, index2, index3)\n",
    "            if temp > length:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        [(clist.append(clist[-1] + c),rlist.append(rlist[-1] + r),hlist.append(hlist[-1] + h))for c,r,h in increase]\n",
    "        result = [-1] * len(requirements)\n",
    "        l = len(clist)\n",
    "        for index,(c,r,t) in enumerate(requirements):\n",
    "            m = max(left(clist,c),left(rlist,r),left(hlist,t))\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        [(clist.append(clist[-1] + c),rlist.append(rlist[-1] + r),hlist.append(hlist[-1] + h))for c,r,h in increase]\n",
    "        result = [-1] * len(requirements)\n",
    "        l = len(clist)\n",
    "        for index,(c,r,t) in enumerate(requirements):\n",
    "            ct = left(clist,c)\n",
    "            rt = left(rlist,r)\n",
    "            ht = left(hlist,t)\n",
    "            m = max(ct,rt,ht)\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        presum1 = [0] + list(accumulate(list(zip(*increase))[0]))\n",
    "        presum2 = [0] + list(accumulate(list(zip(*increase))[1]))\n",
    "        presum3 = [0] + list(accumulate(list(zip(*increase))[2]))\n",
    "        ans, n = [-1] * len(requirements), len(increase) + 1\n",
    "        for i, v in enumerate(requirements):\n",
    "            a, b, c = v\n",
    "            idx1, idx2, idx3 = bisect_left(presum1, a), bisect_left(presum2, b), bisect_left(presum3, c)\n",
    "            if idx1 < n and idx2 < n and idx3 < n:\n",
    "                ans[i] = max(idx1, idx2, idx3)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        c, r, h = [0],[0],[0]\n",
    "        le = len(increase)+1\n",
    "        for l in increase:\n",
    "            c.append(c[-1]+l[0])\n",
    "            r.append(r[-1]+l[1])\n",
    "            h.append(h[-1]+l[2])\n",
    "        res = []\n",
    "        for j in requirements:\n",
    "            rc = bisect.bisect_left(c, j[0])\n",
    "            rr = bisect.bisect_left(r, j[1])\n",
    "            rh = bisect.bisect_left(h, j[2])\n",
    "            rm = max(rc, rr, rh)\n",
    "            if rm == le:\n",
    "                rm = -1\n",
    "            res.append(rm)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as left\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        clist,rlist,hlist = [0],[0],[0]\n",
    "        [(clist.append(clist[-1] + c),rlist.append(rlist[-1] + r),hlist.append(hlist[-1] + h))for c,r,h in increase]\n",
    "        result = [-1] * len(requirements)\n",
    "        l = len(clist)\n",
    "        for index,(c,r,t) in enumerate(requirements):\n",
    "            ct = left(clist,c)\n",
    "            rt = left(rlist,r)\n",
    "            ht = left(hlist,t)\n",
    "            m = max(ct,rt,ht)\n",
    "            if m != l:\n",
    "                result[index] = m\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        n = len(increase) + 1\n",
    "        C, R, H = [0], [0], [0]\n",
    "        for c, r, h in increase:\n",
    "            C.append(C[-1] + c)\n",
    "            R.append(R[-1] + r)\n",
    "            H.append(H[-1] + h)\n",
    "        res = []\n",
    "        for rc, rr, rh in requirements:\n",
    "            resC = bisect.bisect_left(C, rc)\n",
    "            resR = bisect.bisect_left(R, rr)\n",
    "            resH = bisect.bisect_left(H, rh)\n",
    "            r = max(resC, resR, resH)\n",
    "            if r == n:\n",
    "                r = -1\n",
    "            res.append(r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        # 初始化前缀和数组\n",
    "        cPrefix = [0]\n",
    "        rPrefix = [0]\n",
    "        hPrefix = [0]\n",
    "        \n",
    "        # 计算前缀和\n",
    "        for c, r, h in increase:\n",
    "            cPrefix.append(cPrefix[-1] + c)\n",
    "            rPrefix.append(rPrefix[-1] + r)\n",
    "            hPrefix.append(hPrefix[-1] + h)\n",
    "        \n",
    "        # 初始化答案数组\n",
    "        ans = []\n",
    "        \n",
    "        # 检查每个剧情的触发条件\n",
    "        for c, r, h in requirements:\n",
    "            cDay = bisect_left(cPrefix, c)\n",
    "            rDay = bisect_left(rPrefix, r)\n",
    "            hDay = bisect_left(hPrefix, h)\n",
    "            \n",
    "            # 找到三者的最大值作为触发该剧情的最早时间\n",
    "            maxDay = max(cDay, rDay, hDay)\n",
    "            \n",
    "            # 如果有一项永远无法达到，那么剧情无法触发\n",
    "            if maxDay >= len(cPrefix):\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(maxDay)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "# 示例测试\n",
    "sol = Solution()\n",
    "print(sol.getTriggerTime([[2,8,4],[2,5,0],[10,9,8]], [[2,11,3],[15,10,7],[9,17,12],[8,1,14]]))  # 输出 [2, -1, 3, 3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        # 初始化前缀和数组\n",
    "        cPrefix = [0]\n",
    "        rPrefix = [0]\n",
    "        hPrefix = [0]\n",
    "        \n",
    "        # 计算前缀和\n",
    "        for c, r, h in increase:\n",
    "            cPrefix.append(cPrefix[-1] + c)\n",
    "            rPrefix.append(rPrefix[-1] + r)\n",
    "            hPrefix.append(hPrefix[-1] + h)\n",
    "        \n",
    "        # 初始化答案数组\n",
    "        ans = []\n",
    "        \n",
    "        # 检查每个剧情的触发条件\n",
    "        for c, r, h in requirements:\n",
    "            cDay = bisect_left(cPrefix, c)\n",
    "            rDay = bisect_left(rPrefix, r)\n",
    "            hDay = bisect_left(hPrefix, h)\n",
    "            \n",
    "            # 找到三者的最大值作为触发该剧情的最早时间\n",
    "            maxDay = max(cDay, rDay, hDay)\n",
    "            \n",
    "            # 如果有一项永远无法达到，那么剧情无法触发\n",
    "            if maxDay >= len(cPrefix):\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(maxDay)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "# 示例测试\n",
    "sol = Solution()\n",
    "print(sol.getTriggerTime([[2,8,4],[2,5,0],[10,9,8]], [[2,11,3],[15,10,7],[9,17,12],[8,1,14]]))  # 输出 [2, -1, 3, 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        length = len(increase)\n",
    "        C, R, H = [0], [0], [0]\n",
    "        temp_c, temp_r, temp_h = 0, 0, 0\n",
    "        ans = []\n",
    "        for l in increase:\n",
    "            temp_c += l[0]\n",
    "            temp_h += l[1]\n",
    "            temp_r += l[2]\n",
    "            C.append(temp_c)\n",
    "            H.append(temp_h)\n",
    "            R.append(temp_r)\n",
    "        for requirement in requirements:\n",
    "            index1, index2, index3 = self.bisect_left(C, requirement[0]), self.bisect_left(H, requirement[1]), self.bisect_left(R, requirement[2])\n",
    "            temp = max(index1, index2, index3)\n",
    "            if temp > length:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(temp)\n",
    "        return ans\n",
    "\n",
    "    def bisect_left(self, target_list, target):\n",
    "        first, last = 0, len(target_list)-1\n",
    "        while first <= last:\n",
    "            mid = (first + last) // 2\n",
    "            if target <= target_list[mid]:\n",
    "                last = mid - 1\n",
    "            else:\n",
    "                first = mid + 1\n",
    "        return first\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ctable = [0]\n",
    "rtable = [0]\n",
    "htable = [0]\n",
    "\n",
    "class Solution:\n",
    "    def callback(self,  member: list) -> int:\n",
    "        global ctable\n",
    "        global rtable\n",
    "        global htable\n",
    "\n",
    "        cindex = bisect.bisect_left(ctable, member[0])\n",
    "        rindex = bisect.bisect_left(rtable, member[1])\n",
    "        hindex = bisect.bisect_left(htable, member[2])\n",
    "\n",
    "        res = max(cindex, rindex, hindex)\n",
    "\n",
    "        if res == len(ctable):\n",
    "            return -1\n",
    "\n",
    "        return res\n",
    "\n",
    "    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:\n",
    "        global ctable\n",
    "        global rtable\n",
    "        global htable\n",
    "        ctable = [0]\n",
    "        rtable = [0]\n",
    "        htable = [0]\n",
    "\n",
    "        res = []\n",
    "        for i in increase:\n",
    "            ctable.append(ctable[-1] + i[0])\n",
    "            rtable.append(rtable[-1] + i[1])\n",
    "            htable.append(htable[-1] + i[2])\n",
    "\n",
    "        for j in requirements:\n",
    "            day = self.callback(j)\n",
    "            res.append(day)\n",
    "\n",
    "        return res        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
